// Honor Code:
// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
//
//
// apriori 算法
// 刘当一 LeedyPKU@gmail.com
// http://git.oschina.net/Leedy/freq/blob/master/apriori/apriori.cpp
//

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iterator>

using namespace std;

typedef int item;
typedef pair<vector<item>, int> itemset;

bool verbose = false;
bool quiet = false;

void apriori(istream& file, ostream& output, double threshold)
{
	int min_support, max = 0, k = 0, count = 0;		// k: size of itemset
	string tmp_str;
	vector<itemset> C, L;
	vector<vector<item> > origin_data;

	// 先将输入全部读取到内存中，方面之后的操作
	while (getline(file, tmp_str)) {
		stringstream str(tmp_str);
		vector<item> tmp_vec;
		copy(istream_iterator<item>(str), istream_iterator<item>(), back_inserter(tmp_vec));
		origin_data.push_back(tmp_vec);
	}

	// Calculate items
	// 找出输入数据中的最大值，从而初始化 C1
	for (vector<vector<item> >::iterator line = origin_data.begin(); line != origin_data.end(); line++) {
		for (vector<item>::iterator i = line->begin(); i != line->end(); i++) {
			max = max > *i ? max : *i;
		}
		sort(line->begin(), line->end());
	}

	// Construct C1
	// 初始化 C1
	for (item i = 0; i <= max; i++) {
		vector<item> tmp_vec;
		tmp_vec.push_back(i);
		C.push_back(itemset(tmp_vec, 0));
	}

	// Calculate support for C1
	// 计算 C1 的支持度
	for (vector<vector<item> >::iterator line = origin_data.begin(); line != origin_data.end(); line++) {
		for (vector<item>::iterator i = line->begin(); i != line->end(); i++) {
			C[*i].second++;
		}
	}

	// 将最小支持度变为整数，方便比较
	min_support = threshold * origin_data.size();
	if (verbose) {
		cerr << "Total lines: " << origin_data.size() << endl;
		cerr << "Min support: " << min_support << endl;
	}

	// 选出 C 中超过最小支持度的项集，放入 L 中。
	for (vector<itemset>::iterator is = C.begin(); is != C.end(); is++) {
		if (is->second >= min_support) {
			if (!quiet) output << is->first[0] << " : " << is->second << endl;
			++count;
			L.push_back(*is);
		}
	}
	// 清空 L
	C.clear();
	
	k++;		// k = 1
	
	while (!L.empty()) {

		if (verbose)
			cerr << "Join: " << k << "\t" << C.size() << "\t" << L.size() << endl;

		// Join 阶段（从 L 生成新的 C），由 k-1 频繁项集两两合成 k 频繁项集。
		// 设 a,b 为两个 k-1 频繁项集，当且仅当 a_1 = b_1, ... a_(k-2) = b_(k-2), a_(k-1) < b_(k-1),
		// 那么 a_1, ... a_(k-2), a_(k-1), b_(k-1) 为 k 频繁项集。
		for (vector<itemset>::iterator it = L.begin(); it != L.end(); it++) {
			for (vector<itemset>::iterator it2 = it + 1; it < L.end() && it2 < L.end(); it2++) {
				for (int i = 0; i < k - 1; i++) {
					if (it->first[i] != it2->first[i]) {
						goto loopEnd;
					}
				}
				vector<int> array_int(k+1);
				for (int i = 0; i < k+1; i++) {
					array_int[i] = it->first[i];
				}
				array_int[k] = it2->first[k-1];
				C.push_back(itemset(array_int, 0));
			}
		loopEnd:
			;
		}

		k++;

		// cerr << "Trim: " << k << "\t" << C.size() << "\t" << L.size() << endl;

		// Trim 阶段（筛选 C，除去不可能频繁的项集）
		// 优化方法1将其删掉
		/*
		for (auto it = C.begin(); it != C.end();) {
			bool match = false;
			for (const auto& l : L) {
				int i = 0, j = 0;
				while (i < k && j < k-1) {
					if (it->first[i] != l.first[j]) {
						if (i == j) {
							i++;
							continue;
						}
						break;
					}
					i++, j++;
				}
				if (i == k && j == k-1) {
					match = true;
					break;
				}
			}
			if (match) {
				it++;
			} else {
				it = C.erase(it);
			}
		}
		*/

		L.clear();

		if (verbose)
			cerr << "Supp: " << k << "\t" << C.size() << "\t" << L.size() << endl;

		// Calculate support of each itemset
		// Supp 阶段，读取原始数据，计算 C 中每一项的支持度
		for (vector<vector<item> >::iterator line = origin_data.begin(); line != origin_data.end(); line++) {
			int line_size = line->size();
			for (vector<itemset>::iterator is = C.begin(); is != C.end(); is++) {
				int i = 0, j = 0;
				while (i < k && j < line_size) {
					if (is->first[i] == (*line)[j]) {
						i++, j++;
					} else if (is->first[i] < (*line)[j]) {
						break;
					} else {
						j++;
					}
				}
				if (i == k) {
					is->second++;
				}
			}
		}

		if (verbose)
			cerr << "Draw: " << k << "\t" << C.size() << "\t" << L.size() << endl;

		// Get Lk from Ck;
		// Draw 阶段，将 C 中达标的放入 L 中
		for (vector<itemset>::iterator is = C.begin(); is != C.end(); is++) {
			if (is->second >= min_support) {
				if (!quiet) {
					for (int i = 0; i < k; i++) {
						output << is->first[i] << " ";
					}
					output << ": " << is->second << endl;
				}
				++count;
				L.push_back(*is);
			}
		}

		// 清空 C
		C.clear();
	}

	if (quiet) output << count << endl;
}

int main(int argc, char *argv[])
{
	double min_support = 0;
	if (argc > 1)
		min_support = atof(argv[1]);

	// 两种模式，verbose 或 quiet
	// verbose 输出调试信息，quiet 不输出任何信息
    if (argc > 2 && strcmp(argv[2], "-q") == 0)
    	quiet = true;
    if (argc > 2 && strcmp(argv[2], "-v") == 0)
    	verbose = true;

	if (min_support <= 0 || min_support >= 1) {
		cerr << "Invalid min_support " << min_support << " (must between 0 and 1)" << endl;
		return -1;
	}
	// 不同步 stdio，加速输入/输出。
	ios::sync_with_stdio(false);
	apriori(cin, cout, min_support);
	return 0;
}
